Search for: All records

A graph homomorphism is a map between two graphs that preserves adjacency relations. We consider the problem of sampling a random graph homomorphism from a graph into a large network. We propose two complementary MCMC algorithms for sampling random graph homomorphisms and establish bounds on their mixing times and the concentration of their time averages. Based on our sampling algorithms, we propose a novel framework for network data analysis that circumvents some of the drawbacks in methods based on independent and neighborhood sampling. Various time averages of the MCMC trajectory give us various computable observables, including well-known ones such as homomorphism density and average clustering coefficient and their generalizations. Furthermore, we show that these network observables are stable with respect to a suitably renormalized cut dis- tance between networks. We provide various examples and simulations demonstrating our framework through synthetic networks. We also demonstrate the performance of our frame- work on the tasks of network clustering and subgraph classification on the Facebook100 dataset and on Word Adjacency Networks of a set of classic novels. 

Political elites both respond to public opinion and influence it. Elite policy messages can shape individual policy attitudes, but the extent to which they do is difficult to measure in a dynamic information environment. Furthermore, policy messages are not absorbed in isolation, but spread through the social networks in which individuals are embedded, and their effects must be evaluated in light of how they spread across social environments. Using a sample of 358 participants across thirty student organizations at a large Midwestern research university, we experimentally investigate how real social groups consume and share elite information when evaluating a relatively unfamiliar policy area. We find a significant, direct effect of elite policy messages on individuals’ policy attitudes. However, we find no evidence that policy attitudes are impacted indirectly by elite messages filtered through individuals’ social networks. Results illustrate the power of elite influence over public opinion. 

In the parking model on ℤd, each vertex is initially occupied by a car (with probability p) or by a vacant parking spot (with probability 1−p). Cars perform independent random walks and when they enter a vacant spot, they park there, thereby rendering the spot occupied. Cars visiting occupied spots simply keep driving (continuing their random walk). It is known that p=1/2 is a critical value in the sense that the origin is a.s. visited by finitely many distinct cars when p<1/2, and by infinitely many distinct cars when p≥1/2. Furthermore, any given car a.s. eventually parks for p≤1/2 and with positive probability does not park for p>1/2. We study the subcritical phase and prove that the tail of the parking time τ of the car initially at the origin obeys the bounds exp(−C1tdd+2)≤ℙp(τ>t)≤exp(−c2tdd+2) for p>0 sufficiently small. For d=1, we prove these inequalities for all p∈[0,1/2). This result presents an asymmetry with the supercritical phase (p>1/2), where methods of Bramson--Lebowitz imply that for d=1 the corresponding tail of the parking time of the parking spot of the origin decays like e−ct√. Our exponent d/(d+2) also differs from those previously obtained in the case of moving obstacles. 

Background Communicating official public health information about infectious diseases is complicated by the fact that individuals receive much of their information from their social contacts, either via interpersonal interaction or social media, which can be prone to bias and misconception. Objective This study aims to evaluate the effect of public health campaigns and the effect of socially communicated health information on learning about diseases simultaneously. Although extant literature addresses the effect of one source of information (official or social) or the other, it has not addressed the simultaneous interaction of official information (OI) and social information (SI) in an experimental setting. Methods We used a series of experiments that exposed participants to both OI and structured SI about the symptoms and spread of hepatitis C over a series of 10 rounds of computer-based interactions. Participants were randomly assigned to receive a high, low, or control intensity of OI and to receive accurate or inaccurate SI about the disease. Results A total of 195 participants consented to participate in the study. Of these respondents, 186 had complete responses across all ten experimental rounds, which corresponds to a 4.6% (9/195) nonresponse rate. The OI high intensity treatment increases learning over the control condition for all symptom and contagion questions when individuals have lower levels of baseline knowledge (all P values ≤.04). The accurate SI condition increased learning across experimental rounds over the inaccurate condition (all P values ≤.01). We find limited evidence of an interaction between official and SI about infectious diseases. Conclusions This project demonstrates that exposure to official public health information increases individuals’ knowledge of the spread and symptoms of a disease. Socially shared information also facilitates the learning of accurate and inaccurate information, though to a lesser extent than exposure to OI. Although the effect of OI persists, preliminary results suggest that it can be degraded by persistent contradictory SI over time.